<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <title>贪吃蛇</title>
  <style type="text/css">
    * {
      margin: 0;
      padding: 0;
      font-family: "Microsoft YaHei";
    }

    #page {
      margin-right: auto;
      margin-left: auto;
      margin-top: 20px;
      height: 680px;
      width: 980px;
    }

    #yard {
      height: 600px;
      width: 900px;
      border: 1px solid gray;
      box-shadow: 0 0 10px black;
      float: right;
    }

    #mark {
      font-weight: 800;
    }

    #mark_con {
      color: red;
    }

    #speed {
      font-weight: 800;
    }

    #speed_con {
      color: red;
    }

    button {
      width: 50px;
    }

    a {
      text-decoration: none;
    }
  </style>
  <script type="text/javascript">
    //常量
    const NEIBOR_NUM_MAX = 4;
    const UP = 0;
    const DOWN = 1;
    const LEFT = 2;
    const RIGHT = 3;

    //伪常量
    var BLOCK_SIZE = 15; //格子大小
    var COLS = 60; //列数
    var ROWS = 40; //行数

    //变量
    var snakes = []; //保存蛇坐标
    var tail; //蛇尾
    var c = null; //绘图对象
    var toGo = 3; //行进方向
    var snakecount = 1; //蛇身数量
    var interval = null; //计时器
    var foodX = 0; //食物X轴坐标
    var foodY = 0; //食物Y轴坐标
    var oMark = null; //分数显示框
    var oSpeed = null; //速度显示框
    var isPause = false; //是否暂停
    async function sleep(ms) {
      return new Promise((resolve) => setTimeout(resolve, ms));
    }

    var AIpath = [];

    //优先队列 https://juejin.cn/post/7045279421334290446
    class PriorityQueue {
      constructor(compare) {
        if (typeof compare !== "function") {
          throw new Error("compare function required!");
        }

        this.data = [];
        this.compare = compare;
        this.length = 0;
      }
      //二分查找 寻找插入位置
      search(target) {
        let low = 0,
          high = this.data.length;
        while (low < high) {
          let mid = low + ((high - low) >> 1);
          if (this.compare(this.data[mid], target) > 0) {
            high = mid;
          } else {
            low = mid + 1;
          }
        }
        return low;
      }
      //添加
      push(elem) {
        // console.log("elem=", elem);
        // console.log("data.length=", this.data.length);
        let index = this.search(elem);
        this.data.splice(index, 0, elem);
        // console.log("data.length=", this.data.length);

        this.length = this.data.length;
        return this.data.length;
      }
      //取出最优元素
      pop() {
        // console.log("this.data=", this.data);
        // console.log("data.length=", this.data.length);

        // for (var i = 0; i < this.data.length; i++) {
        //   console.log("data[", i, "]=", this.data[i]);
        // }
        this.length--;
        return this.data.pop();
      }

      //判断是否为空
      empty() {
        return 0 === this.data.length;
      }
    }
    class Node {
      constructor(x, y) {
        this.x = x;
        this.y = y;
        this.g = 0;
        this.h = 0;
        this.f = 0;
        this.open = false;
        this.close = false;
        this.parent = null;
        this.walkable = true;
      }
      moveToClose() {
        this.open = false;
        this.close = true;
      }
      moveToOpen() {
        this.open = true;
        this.close = false;
      }
    }
    class Map {
      constructor() {
        //创建二维地图,用于规划贪吃蛇路径
        this.mapForAI = new Array(ROWS);
        for (var i = 0; i < ROWS; i++) {
          this.mapForAI[i] = new Array(COLS);
          for (var j = 0; j < COLS; j++) {
            this.mapForAI[i][j] = new Node(j, i); //x是COL,y是ROW,别弄错了
          }
        }

        //初始化不可通行节点
        snakes.forEach((curr) => {
          this.mapForAI[curr.y][curr.x].walkable = false;
        });

        //console.log(this.mapForAI);
      }

      getNeibors(center) {
        var r, c, i;
        var neibors = new Array(NEIBOR_NUM_MAX);

        for (i = 0; i < NEIBOR_NUM_MAX; i++) {
          neibors[i] = null;
        }

        r = center.y;
        c = center.x;

        if (r > 0) neibors[UP] = this.mapForAI[r - 1][c];

        if (r < ROWS - 1) neibors[DOWN] = this.mapForAI[r + 1][c];

        if (c > 0) neibors[LEFT] = this.mapForAI[r][c - 1];

        if (c < COLS - 1) neibors[RIGHT] = this.mapForAI[r][c + 1];

        //console.log(neibors);
        return neibors;
      }
    }

    function abs(x) {
      return x >= 0 ? x : -x;
    }
    function getManhattan(a, b) {
      return abs(a.x - b.x) + abs(a.y - b.y);
    }
    //获取从起点到终点的路径,如果存在则返回路径数组，不存在则返回空数组
    function getPath(src, dst) {
      let havePath = false;
      var path = [];
      var neibors;
      //初始化mapForAI
      map = new Map();

      //构建优先队列
      var openList = new PriorityQueue((n1, n2) => n2.f - n1.f);

      //调用A星算法
      // console.log("src=", src);
      // console.log("dst=", dst);
      var current = map.mapForAI[src.y][src.x];
      // console.log("current=", current);
      openList.push(current);
      current.moveToOpen();
      while (false === openList.empty()) {
        // console.log("openList=", openList);
        current = openList.pop();
        // console.log("current=", current);
        current.moveToClose();

        if (current.x === dst.x && current.y === dst.y) {
          havePath = true;
          break;
        }
        neibors = map.getNeibors(current);
        for (i = 0; i < NEIBOR_NUM_MAX; i++) {
          if (
            null === neibors[i] ||
            false === neibors[i].walkable ||
            true === neibors[i].close
          ) {
            continue;
          }

          if (false === neibors[i].open) {
            neibors[i].g = current.g + 1;
            neibors[i].h = getManhattan(neibors[i], dst);
            neibors[i].f = neibors[i].g + neibors[i].h;
            neibors[i].moveToOpen();
            neibors[i].parent = current;
            // console.log("neibors[i]=", neibors[i]);
            openList.push(neibors[i]);
            // console.log("openList=", openList);
          } else if (true === neibors[i].open) {
            g = current.g + 1;
            if (g < neibors[i].g) {
              neibors[i].g = g;
              neibors[i].f = neibors[i].g + neibors[i].h;
              neibors[i].parent = current;
            }
          }
        }
      }

      // console.log("havePath=", havePath);
      //返回路径数组
      if (havePath) {
        current = map.mapForAI[dst.y][dst.x];
        while (null != current.parent) {
          path.unshift(current);
          current = current.parent;
        }
      }
      drawPath(path);

      return path;
    }

    //画路径
    async function drawPath(path) {
      await sleep(1000);
      for (var i = 0; i < path.length; i++) {
        c.beginPath();
        c.fillStyle = "blue";
        c.fillRect(
          path[i].x * BLOCK_SIZE,
          path[i].y * BLOCK_SIZE,
          BLOCK_SIZE,
          BLOCK_SIZE
        );
        c.closePath();
      }
    }
    // 绘图函数
    function draw() {
      c.clearRect(0, 0, BLOCK_SIZE * COLS, BLOCK_SIZE * ROWS);
      //画出横线
      for (var i = 1; i <= ROWS; i++) {
        c.beginPath();
        c.moveTo(0, i * BLOCK_SIZE);
        c.lineTo(BLOCK_SIZE * COLS, i * BLOCK_SIZE);
        c.strokeStyle = "gray";
        c.stroke();
      }
      //画出竖线
      for (var i = 1; i <= COLS; i++) {
        c.beginPath();
        c.moveTo(i * BLOCK_SIZE, 0);
        c.lineTo(i * BLOCK_SIZE, BLOCK_SIZE * ROWS);
        c.stroke();
      }
      //画出蛇
      for (var i = 0; i < snakes.length; i++) {
        c.beginPath();
        c.fillStyle = "green";
        c.fillRect(
          snakes[i].x * BLOCK_SIZE,
          snakes[i].y * BLOCK_SIZE,
          BLOCK_SIZE,
          BLOCK_SIZE
        );
        //绘制边框
        // c.moveTo(snakes[i].x, snakes[i].y);
        // c.lineTo(snakes[i].x + BLOCK_SIZE, snakes[i].y);
        // c.lineTo(snakes[i].x + BLOCK_SIZE, snakes[i].y + BLOCK_SIZE);
        // c.lineTo(snakes[i].x, snakes[i].y + BLOCK_SIZE);
        c.closePath();
        // c.strokeStyle = "white";
        // c.stroke();
      }
      //画出食物
      c.beginPath();
      c.fillStyle = "yellow";
      c.fillRect(
        foodX * BLOCK_SIZE,
        foodY * BLOCK_SIZE,
        BLOCK_SIZE,
        BLOCK_SIZE
      );
      // c.moveTo(foodX, foodY);
      // c.lineTo(foodX + BLOCK_SIZE, foodY);
      // c.lineTo(foodX + BLOCK_SIZE, foodY + BLOCK_SIZE);
      // c.lineTo(foodX, foodY + BLOCK_SIZE);
      c.closePath();
      // c.strokeStyle = "red";
      // c.stroke();
    }
    //游戏初始化
    function start() {
      for (var i = 0; i < snakecount; i++) {
        snakes[i] = { x: i, y: 0 };
      }
      addFood();
      draw();
      oMark.innerHTML = 0; //分数初始为 0
      speed = 10; //速度初始为 10
      oSpeed.innerHTML = speed.toString();
    }

    //AI移动函数
    function AImove() {
      var food = { x: 0, y: 0 };
      food.x = foodX;
      food.y = foodY;
      if (0 === AIpath.length) {
        head = snakes[snakecount - 1];
        AIpath = getPath(head, food);
        // console.log("AIPath=", AIpath);
      }
      next = AIpath.shift();
      snakes.push({ x: next.x, y: next.y });
      tail = snakes.shift(); //shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值
      isEat();
      isDie();
      draw();
    }
    //吃到食物判断
    function isEat() {
      head = snakes[snakecount - 1];
      if (head.x == foodX && head.y == foodY) {
        oMark.innerHTML = (parseInt(oMark.innerHTML) + 1).toString(); //分数+1
        addFood(); //新增食物
        addSnake(); //蛇身长度+1
      }
    }
    //添加蛇身
    function addSnake() {
      snakecount++;
      snakes.unshift(tail); //unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度
    }
    //交互响应函数
    function keydown(keyCode) {
      switch (keyCode) {
        case 37: //左边
          if (toGo != 1 && toGo != 3) toGo = 1;
          break;
        case 38: //上边
          if (toGo != 2 && toGo != 4) toGo = 2;
          break;
        case 39: //右边
          if (toGo != 3 && toGo != 1) toGo = 3;
          break;
        case 40: //下的
          if (toGo != 4 && toGo != 2) toGo = 4;
          break;
        case 80: //开始/暂停
          if (isPause) {
            interval = setInterval(move, 100);
            isPause = false;
            document.getElementById("pause").innerHTML = "P暂停";
          } else {
            clearInterval(interval);
            isPause = true;
            document.getElementById("pause").innerHTML = "P开始";
          }
          break;
        case 81: //速度增加
          speed += 1;
          oSpeed.innerHTML = speed.toString();
          clearInterval(interval);
          interval = setInterval(AImove, 1000 / speed);
          break;
        case 82: //速度降低
          speed -= 1;
          oSpeed.innerHTML = speed.toString();
          clearInterval(interval);
          interval = setInterval(AImove, 1000 / speed);
          break;
      }
    }
    //制造食物
    function addFood() {
      foodX = Math.floor(Math.random() * (COLS - 1));
      foodY = Math.floor(Math.random() * (ROWS - 1));
      // console.log(foodX + " -- " + foodY);
    }
    //死亡判断
    function isDie() {
      head = snakes[snakecount - 1];
      if (head.x < 0 || head.x == COLS || head.y < 0 || head.y == ROWS) {
        alert("撞墙死亡");
        clearInterval(interval);
      }
      for (var i = 0; i < snakecount - 1; i++) {
        if (head.x == snakes[i].x && head.y == snakes[i].y) {
          clearInterval(interval);
          alert("撞自己死亡");
        }
      }
    }
    // 启动函数
    window.onload = function () {
      c = document.getElementById("canvas").getContext("2d");
      oMark = document.getElementById("mark_con");
      oSpeed = document.getElementById("speed_con");
      oSpeed.innerHTML = speed.toString();
      start();
      interval = setInterval(AImove, 1000 / speed); //每1000/speed 调用一次 move
      document.onkeydown = function (event) {
        var event = event || window.event;
        keydown(event.keyCode);
      };
    };
  </script>
</head>

<body>
  <div id="page">
    <div id="yard">
      <canvas id="canvas" height="600px" width="900px"></canvas>
    </div>
    <div id="help">
      <div id="mark">得分：<span id="mark_con"></span></div>
      <div id="speed">
        速度: <span id="speed_con"></span>
        <table>
          <tr>
            <td><button onclick="keydown(81);">+</button></td>
          </tr>
          <tr>
            <td><button onclick="keydown(82);">-</button></td>
          </tr>
        </table>
      </div>
    </div>
  </div>
  <div style="text-align: center">
    <div id="helper">
      <a href="index.html">再玩一次</a><span></span>
      <a href="indexManual.html">再玩一次(手动版)</a>
    </div>
    <p>作者: 小白菜</p>
  </div>
</body>

</html>